package arithmetic.demo24;

import java.util.Arrays;


/**
 *  题目： 贪心_优势洗牌
 */


class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        // 初始化
        Integer[] index = new Integer[n];
        for(int i = 0; i < n; i++) {
            index[i] = i;
        }

        // 先对nums1 排序
        Arrays.sort(nums1);
        // 排序
        Arrays.sort(index, (a,b)->{
          return   nums2[a] - nums2[b];
        });

        // 临时存储
        int[] tmp = new int[n];
        int[] ret = new int[n];
        int right = n- 1, left = 0; 

        // 利用下标排序找出升序的元素
        for(int i =0; i < n; i++) {
            if(nums1[i] > nums2[index[left]]){
                // 如果大就直接得分
                tmp[left++] = nums1[i]; 
            } else {
                // 如果小就拉下最大的
                tmp[right--] = nums1[i]; 
            }
        }


        // 存储结果
        for(int i = 0; i < n ; i++) {
            ret[index[i]] = tmp[i];
        }

        return ret;
    }
}


/**
 * 题目： 简单多状态dp_删除并获得点数
 */

class Solution1 {
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        // 准备工作
        // 将这个问题转化成打家劫舍问题思考
        int[] hash = new int[40000];
        int max = nums[0];
        for(int x: nums) {
            hash[x]++;
            max = Math.max(x, max);
        }


        // 进行打家劫舍

        // 创建 dp
        int[] fp = new int[max+1], gp = new int[max + 1];
        for(int i =1; i < max + 1 ; i++) {
            // 当前位置需要选的
            fp[i] = gp[i-1] + (hash[i] * i);

            // 当前位置不选的
            gp[i] = Math.max(gp[i-1] , fp[i-1]);
        }

        return Math.max(gp[max] , fp[max]);



    }
}



